package com.二叉树2;

import java.util.*;

/**
 *   Binary Tree Level Order Traversal
 *
 * Solution
 * Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
 *
 * For example:
 * Given binary tree [3,9,20,null,null,15,7],
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * return its level order traversal as:
 * [
 *   [3],
 *   [9,20],
 *   [15,7]
 * ]
 * https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/931/
 */
public class 顺序遍历 {
    static class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {

            LinkedList<TreeNode> node = new LinkedList();
            List<List<Integer>> list=new ArrayList<>();
            if(root!=null){
                node.add(root);
            }
            while(!node.isEmpty()){
                int size=node.size();
                List current=new ArrayList();
                for(int i=0;i<size;i++){
                    TreeNode temp=node.poll();
                    current.add(temp.val);
                    if(temp.left!=null){
                        node.add(temp.left);
                    }
                    if(temp.right!=null){
                        node.add(temp.right);
                    }
                }
                list.add(current);
            }
            return list;


        }
        public List<List<Integer>> levelOrder2(TreeNode root) {
            List<List<Integer>> lists = new ArrayList<>();
            if(root==null){
                return lists;
            }
            Queue<TreeNode> stack = new LinkedList<>();
            stack.add(root);

            while (!stack.isEmpty()){
                List<Integer> list = new ArrayList<>();
                int size = stack.size();
                for(int i = 0;i< size;i++){
                    TreeNode treeNode = stack.poll();
                    list.add(treeNode.val);
                    if(treeNode.left != null){
                        stack.add(treeNode.left);
                    }
                    if(treeNode.right != null){
                        stack.add(treeNode.right);
                    }
                }
                lists.add(list);
            }
        return lists;
        }

        public static void main(String[] args) {
            Solution solution = new Solution();
            List<List<Integer>> lists = solution.levelOrder2(new TreeNode(new int[]{1, 2, 3,4,5,6,7}));
        }
    }
}
